//1.大神解法
class Solution {
public:
    string decodeString(string s) {
        string ans;
        stack<pair<int, int>> stk;
        int count = 0;
        for (auto x : s) {
            if (isdigit(x)) 
                count = 10 * count + (x - '0');
            else if (x == '[') {
                stk.push({count, ans.size()});
                count = 0;
            }
            else if (isalpha(x)) 
                ans += x;
            else if (x == ']') {
                int n = stk.top().first;
                string str = ans.substr(stk.top().second, ans.size() - stk.top().second);
                for (int i = 0; i < n - 1; i++) {
                    ans += str;
                }
                stk.pop();
            }
        }
        return ans;
    }
}; 

//2.题解--栈
class Solution {
public:
    string decodeString(string s) {
        stack<int> numStack;
        stack<string> strStack;
        int curNum = 0;
        string curStr;
        
        for (char ch : s) {
            if (isdigit(ch)) {
                // 多位数字累加
                curNum = curNum * 10 + (ch - '0');
            }
            else if (ch == '[') {
                // 进入新层，保存当前层状态
                numStack.push(curNum);
                strStack.push(curStr);
                curNum = 0;
                curStr.clear();
            }
            else if (ch == ']') {
                // 退出一层，弹出重复次数和上一层字符串
                int k = numStack.top(); 
                numStack.pop();
                string prev = strStack.top(); 
                strStack.pop();
                
                // 预留空间并拼接
                string tmp;
                tmp.reserve(prev.size() + curStr.size() * k);
                tmp += prev;
                for (int i = 0; i < k; ++i) {
                    tmp += curStr;
                }
                curStr.swap(tmp);
            }
            else {
                // 普通字母累加
                curStr.push_back(ch);
            }
        }
        
        return curStr;
    }
};

